package cn.edu.xjtu.data_structure.experiment.ex_1;

/**
 * @author yjq
 * @version 1.0
 * @date 2021/10/23 10:13
 */
public class BigNumber {
    String origin;//原有字符串
    char[] nums;//字符数组

    public BigNumber(String origin) {
        this.origin = origin;
        nums = origin.toCharArray();
    }

    /**
     * 大整数相加
     *
     * @param big1
     * @param big2
     * @return 大整数
     */
    public static BigNumber add(BigNumber big1, BigNumber big2) {
        if (big1.nums[0] == '-') {
            BigNumber big3 = new BigNumber(big1.origin.substring(1));
            return subtract(big2, big3);
        }//如果被加数是负数，则转换为减法
        if (big2.nums[0] == '-') {
            BigNumber big3 = new BigNumber(big2.origin.substring(1));
            return subtract(big1, big3);
        }//如果加数是负数，则转换为减法
        if (big1.nums.length < big2.nums.length) {
            BigNumber temp = big1;
            big1 = big2;
            big2 = temp;
        }//如果被加数位数<加数，则交换
        int len1 = big1.nums.length, len2 = big2.nums.length;
        int carry = 0;//进位
        String s = "";
        for (int i = 0; i < len2; i++) {
            int result = (big1.nums[len1 - 1 - i] - '0') + (big2.nums[len2 - 1 - i] - '0') + carry;
            int bit = result % 10;
            carry = result / 10;
            s += bit;
        }//倒转来算，先算低位的重合部分
        for (int j = len2; j < len1; j++) {
            int result = (big1.nums[len1 - 1 - j] - '0') + carry;
            int bit = result % 10;
            carry = result / 10;
            s += bit;
        }
        if (carry > 0)
            s += '1';
        String r = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            r += s.charAt(i);
        }
        return new BigNumber(removeZero(r));
    }

    /**
     * 大整数相减
     *
     * @param big1 被减数
     * @param big2 减数
     * @return 相减结果
     */
    public static BigNumber subtract(BigNumber big1, BigNumber big2) {

        {
            if (big1.nums[0] == '-') {
                BigNumber big3 = new BigNumber(big1.origin.substring(1));
                if (big2.nums[0] == '-') {
                    BigNumber big4 = new BigNumber(big2.origin.substring(1));
                    return subtract(big4, big3);//负数减去负数
                } else {
                    return new BigNumber('-' + add(big3, big2).origin);
                    //负数减去正数则转换为加法
                }
            }else{
                if (big2.nums[0] == '-'){
                    BigNumber big5 = new BigNumber(big2.origin.substring(1));
                    return add(big1,big5);
                }
            }

            if (low(big1.origin,big2.origin)) {//当被减数小于减数
                BigNumber temp = big1;
                big1 = big2;
                big2 = temp;
                BigNumber bigNumber = subtract(big1, big2);
                return new BigNumber('-' + bigNumber.origin);
            }
            char[] s = big1.nums;
            for (int bi = big2.origin.length() - 1, si = s.length - 1; si >= 0; si--, bi--) {
                //相减
                if ((s[si] -= (bi >= 0 ? big2.origin.charAt(bi) - '0' : 0)) < '0') {
                    s[si] += 10;
                    s[si - 1]--;//借位
                }
            }

            String result = "";
            for (int i = 0; i < s.length; i++) {
                result += s[i];
            }
            return new BigNumber(removeZero(result));
        }
    }

    /**
     * 大整数乘法
     *
     * @param b
     * @return 乘法结果
     */
    public BigNumber multiply(BigNumber b) {
        StringBuffer aa, bb;
        int n = 0;
        if (this.nums[0] == '-') {
            aa = new StringBuffer(this.origin.substring(1));//去掉负号
            n++;
        } else aa = new StringBuffer(this.origin);
        if (b.nums[0] == '-') {
            bb = new StringBuffer(b.origin.substring(1));//去掉负号
            n++;
        } else bb = new StringBuffer(b.origin);

        char s[] = new char[aa.length() + bb.length()];//存储运算结果
        for (int i = 0; i < s.length; i++) {
            s[i] = '0';
        }//初始化计算结果数组
        aa.reverse();
        bb.reverse();
        for (int j = 0; j < bb.length(); j++) {
            if (bb.charAt(j) == '0') continue;
            int temp = 0;
            for (int i = 0; i < aa.length(); i++) {
                temp += (aa.charAt(i) - '0') * (bb.charAt(j) - '0') + (s[j + i] - '0');
                s[j + i] = (char) (temp % 10 + '0');
                temp /= 10;
            }
            s[aa.length() + j] += temp;//进位
        }
        String ss = "";
        for (int i = s.length - 1; i >= 0; i--) {
            ss += s[i] + "";
        }
        ss = removeZero(ss);//去掉前导0
        String sign = "";
        if (n == 1)
            sign = "-";//负数
        return new BigNumber(sign + ss);
    }

    /**
     * 比较a是否小于b
     *
     * @param a
     * @param b
     * @return a<b返回true ， 否则为true
     */
    public static Boolean low(String a, String b) {
        if (a.length() < b.length())
            return true;
        else if (a.length() > b.length())
            return false;
        else {
            if (a.compareTo(b) < 0)
                return true;
            else
                return false;
        }
    }

    /**
     * 大整数除法
     *
     * @param a 被除数
     * @param b 除数
     * @return
     */
    public static BigNumber divide(BigNumber a, BigNumber b) {
        int n = 0;
        String aa;
        String bb;
        if (a.nums[0] == '-') {
            n++;
            aa = (a.origin.substring(1));//去掉负号
        } else {
            aa = a.origin;
        }
        if (b.nums[0] == '-') {
            n++;
            bb = (b.origin.substring(1));//去掉负号
        } else {
            bb = b.origin;
        }
        if (low(a.origin, b.origin)) {
            return new BigNumber("0");
        }
        String s = "", c;

        c = aa.substring(0, bb.length() - 1);
        for (int i = bb.length() - 1; i < aa.length(); i++) {
            int count = 0;
            for (c = (c.equals("0") ? " " : c) + aa.charAt(i); !low(c, bb); count++)
                c = subtract(new BigNumber(c), new BigNumber(bb)).origin;//利用减法演算除法
            s += count + "";
        }
       s= s.charAt(0) == '0' ? s.substring(1) : s;
        if (n==1) s='-'+s;
        return new BigNumber(s);
    }

    /**
     * 清除前导0
     * @param s
     * @return
     */
    public static String removeZero(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '0') {
                return s.substring(i);
            }
        }
        return "0";
    }

}
